package main

import (
	"fmt"
)

//  选择排序
func findMaxR(arr []int) int {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr[0]
	} else {
		max := arr[0]

		for i := 0; i < length; i++ {
			if arr[i] > max {
				max = arr[i]
			}
		}
		return max
	}
}

//划分几个桶
func radixSort(arr []int) []int {
	//寻找数组中最大的数值
	max := findMaxR(arr)

	for bit := 1; max/bit > 1; bit *= 10 { //每次处理一个级别位的数据
		arr = bitSort(arr, bit)

		// break
		//fmt.Println(arr)
	}
	return arr
}

//
func bitSort(arr []int, bit int) []int {
	length := len(arr)
	bitCount := make([]int, 11)
	for i := 0; i < length; i++ {
		num := (arr[i] / bit) % 10 // //分层处理，bit=1000的，三位数不参与排序了，bit=10000的四位数不参与排序
		// fmt.Println(num)
		bitCount[num]++ ////统计余数相等个数
	}
	fmt.Println("取余", bit, "数位", bitCount) //对应余数在桶的个数

	for i := 1; i < 11; i++ {
		bitCount[i] += bitCount[i-1] //叠加，计算位置
	}

	fmt.Println("叠加的数量", bitCount)

	tmp := make([]int, 11) //开辟临时数组
	for i := length - 1; i >= 0; i-- {
		num := (arr[i] / bit) % 10
		tmp[bitCount[num]-1] = arr[i]
		bitCount[num]--
	}

	fmt.Println("临时数组：", tmp)

	for i := 0; i < length; i++ {
		arr[i] = tmp[i] //保存数组
	}

	fmt.Println(arr)
	fmt.Println()

	//fmt.Println(tmp)

	return arr
}

/**

	[4418 59 3 456 456 4552 449 670 788 1377 2656]
	取余 1 数位 [1 0 1 1 0 0 3 1 2 2 0]
	叠加的数量 [1 1 2 3 3 3 6 7 9 11 11]
	临时数组： [670 4552 3 456 456 2656 1377 4418 788 59 449]
	[670 4552 3 456 456 2656 1377 4418 788 59 449]

	取余 10 数位 [1 1 0 0 1 5 0 2 1 0 0]
	叠加的数量 [1 2 2 2 3 8 8 10 11 11 11]
	临时数组： [3 4418 449 4552 456 456 2656 59 670 1377 788]
	[3 4418 449 4552 456 456 2656 59 670 1377 788]

	取余 100 数位 [2 0 0 1 4 1 2 1 0 0 0]
	叠加的数量 [2 2 2 3 7 8 10 11 11 11 11]
	临时数组： [3 59 1377 4418 449 456 456 4552 2656 670 788]
	[3 59 1377 4418 449 456 456 4552 2656 670 788]

	取余 1000 数位 [7 1 1 0 2 0 0 0 0 0 0]
	叠加的数量 [7 8 9 9 11 11 11 11 11 11 11]
	临时数组： [3 59 449 456 456 670 788 1377 2656 4418 4552]
	[3 59 449 456 456 670 788 1377 2656 4418 4552]


**/

// 木桶排序
func main() {
	arr := []int{4418, 59, 3, 456, 456, 4552, 449, 670, 788, 1377, 2656}

	fmt.Println(arr)

	radixSort(arr)
}
